Leetcode 1498

Todays question is bit harder than previous sliding window, because of findint the apparch , note we only need the min and max to determine if subsequnce between would be valid or not.

class Solution {
    public int numSubseq(int[] nums, int target) {
        // still two pointer problem 
        int n = nums.length;
        int MOD = 1000000007;
        Arrays.sort(nums);

        // compute the value of 2 to the power of each value
        int[] power = new int[n];
        power[0] = 1;
        for(int i = 1; i < n; i ++){
            power[i] = (power[i - 1] * 2) % MOD;
        }

        int res = 0;
        int left = 0, right = n - 1;
        while(left <= right){
            if(nums[left] + nums[right] <= target){
                // what this means is the min at left and max at right,
                // there are 2 ^ right - left subsequence that have nums[left] as the min and nums[right] as max, all theses subsequence is meeting our requirement.
                res += power[right - left];
                res %= MOD;
                left ++;
            }else{
                // max is too big, we shrink the window.
                right --;
            }
        }
        return res;
    }
}